import java.util.LinkedList;
import java.util.Queue;

/**
 * 733. 图像渲染
 * https://leetcode.cn/problems/flood-fill/description/
 */
class Solution {
    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        int prev = image[sr][sc];
        if(color == prev) return image;
        //层序遍历bfs
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{sr, sc});
        image[sr][sc] = color;

        while(!q.isEmpty()) {
            int[] arr = q.poll();
            int x = arr[0], y = arr[1];
            for(int i = 0; i < 4; i++) {
                if(x + dx[i] >=0 && x + dx[i] < image.length
                        && y + dy[i] >= 0 && y + dy[i] < image[0].length
                        && image[x + dx[i]][y + dy[i]] == prev) {
                    image[x + dx[i]][y + dy[i]] = color;
                    q.add(new int[]{x + dx[i], y + dy[i]});
                }

            }
        }

        return image;
    }
}